package com.algorithm.search;

import com.algorithm.sort.Sort;

/**
 * Created by mu on 2018/2/6.
 */
public class Find {
    public static void main(String[] args) {
        int[] array = new int[]{3,2,5,4,8,7,6,9};//RandomUtil.randomArray(100, 0, 100);
        new Sort().heapSort(array);
        Find find = new Find();
        System.out.println(find.halfSearch1(array,0,array.length-1,345));
        System.out.println(find.halfSearch2(array,453));
    }
    /**
     * 递归
     * @param array
     * @return
     */
    private int halfSearch1(int[] array,int low,int high,int key) {
        if(low>high)
            return -1;
        else{
            int mid=(high+low)/2;
            int index;
            if(key>array[mid])
                index=halfSearch1(array,mid+1,high,key);
            else if(key<array[mid])
                index=halfSearch1(array,low,mid-1,key);
            else
                index=mid;
            return index;
        }

    }

    /**
     * 非递归
     * @param array
     * @return
     */
    private int halfSearch2(int[] array,int key) {
        int high=array.length-1,low=0;
        int mid;
        while(low<=high){
             mid=(low+high)/2;
             if(key>array[mid])
                 low=mid+1;
             else if(key<array[mid])
                 high=mid-1;
             else if(key==array[mid])
                 return mid;
        }
        return -1;
    }
}
